1135. Connecting Cities With Minimum Cost
Medium

There are n cities numbered from 1 to n.

You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together.  (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.)

Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together.  The cost is the sum of the connection costs used. If the task is impossible, return -1.

 

Example 1:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: 
Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2:

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: 
There is no way to connect all cities even if all edges are used.

 

Note:

  1. 1 <= n <= 10000
  2. 1 <= connections.length <= 10000
  3. 1 <= connections[i][0], connections[i][1] <= n
  4. 0 <= connections[i][2] <= 105
  5. connections[i][0] != connections[i][1]
Accepted
30,255
Submissions
50,455
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
What if we model the cities as a graph?
Show Hint 2
Build a graph of cities and find the minimum spanning tree.
Show Hint 3
You can use a variation of the Kruskal's algorithm for that.
Show Hint 4
Sort the edges by their cost and use a union-find data structure.
Show Hint 5
How to check all cities are connected?
Show Hint 6
At the beginning we have n connected components, each time we connect two components the number of connected components is reduced by one. At the end we should end with only a single component otherwise return -1.

Average Rating: 4.46 (13 votes)

Premium

Solution


Approach 1: Minimum Spanning Tree (Using Kruskal's algorithm)

Intuition

If we model the cities and connections as a graph, each connection is an edge (undirected) and each city is a node of the graph. We need to find a subset of edges which connects all the nodes of the graph with the minimum possible total weight. This is by definition the Minimum Spanning Tree or MST of a graph.

Algorithm

There are a variety of algorithms that we can use to obtain the MST of a graph. We will use Kruskal's algorithm here, which is implemented using the Disjoint set Union-Find data structure.

In order to obtain the MST using Kruskal's algorithm, we first sort all the connections (edges) present in the graph based on their weights (in increasing order) and will iterate over them one by one. The objective here is to greedily pick edges that will help us to connect more nodes in the graph. Each time we find a new edge which does not result in a cycle with the edges selected so far, we add that edge in the final MST. We keep doing this till we have obtained the MST which connects all the nodes in the graph (i.e. connects all the cities using the connections).

Disjoint-set union find can be implemented in a couple of ways. A plain union find is shown below which keeps the track of the parent of each node (initially parent of i is set to itself, i.e. i) and performs the union and find using a helper method getRoot.

The above implementation can be made faster by incorporating Path compression. Here, while obtaining the root, we compress the path by assigning the grandparent of the node as the parent (thereby skipping connections and moving nodes closer to the root). We modify the Find method to implement path compression.

This can be made even faster using a technique known as Weighted Union. In this technique, in addition to the parent nodes, we also keep the weights of each of the nodes. Every time we take union, the root node with more weight (i.e. having more elements in the corresponding set) is used as the parent node of the other node. We initialize the weight corresponding to each node as 1 initially, as each element belongs to it's own set in the beginning. Below is the implementation of this idea (we modify Union method).

If we combine both Path compression and Weighted Union, it takes logN\log^{\ast} N for the union and find operations in case of Disjoint-set union link. Here logN\log^{\ast} N is an extremely slow-growing inverse Ackermann function a.k.a Iterated logarithm and practically does not exceed 5. Hence it can be treated as a constant for implementation purposes.

We can combine all the concepts we have seen above in order to implement Kruskal's algorithm for obtaining MST of a graph. Below is the implementation of this.

Complexity Analysis

  • Time complexity: Assuming NN to be the total number of nodes (cities) and MM to be the total number of edges (connections). Sorting all the MM connections will take O(MlogM)O(M \cdot \log M). Performing union find each time will take logN\log^{\ast} N (Iterated logarithm). Hence for M edges, it's O(MlogN)O(M \cdot \log^{\ast} N) which is practically O(M)O(M) as the value of iterated logarithm, logN\log^{\ast} N never exceeds 5.

  • Space complexity: O(N), space required by parents and weights.

Report Article Issue

Comments: 7
bkvvldmr's avatar
Read More

While it's a nice problem to learn new algorithm at the same time this is absolutely disgusting job interview question. Not even mentioning the fact that Kruskal didn't come up with this idea in 45 minutes, the most important thing is that there is a very low space for candidate to show his ability to solve problems. The best INTERVIEW questions (maybe even hard, final complexity doesn't matter) can be solved using easy "brute force" ideas but they should allow candidates to iteratively improve the initial solution to come up with the most optimal (most optimal that candidate came up with in 45 mins). And this path from the simple naive idea to something more optimal (plus candidate's ability to communicate and think about complexity of his solution) is the most crucial thing for interviewer to evaluate candidate and give a hire/no hire recommendation.
So, what I want to say: fck this kind of INTERVIEW questions. But I love that this problem helps me to learn smth new (or forgotten old :).

53
Show 4 replies
Reply
Share
Report
lj1270's avatar
Read More

Well... I don't think I can pass a minimum spanning tree question like this.

5
Reply
Share
Report
happykimi's avatar
Read More

The weight in DisjointSet is useless!?

1
Reply
Share
Report
gururaj88's avatar
Read More

Much cleaner solution Python3: Straightforward Kruskal and UnionFind algorithm
Runtime: 804 ms, faster than 17.54% of Python3 online submissions for Connecting Cities With Minimum Cost.
Memory Usage: 20.3 MB, less than 31.98% of Python3 online submissions for Connecting Cities With Minimum Cost.

class UnionFind:
    
    def __init__(self, N):
        self.ufid = [i for i in range (N + 1)]
        
    def find(self, node):
        root = node
        while root != self.ufid[root]:
            root = self.ufid[root]
        
        # path compresssion
        p = node
        while p != root:
            parent = self.ufid[p]
            self.ufid[p] = root
            p = parent
        
        return root            
        
        
    def union(self, x, y):
        root1, root2 = self.find(x), self.find(y)
        
        if root1 == root2:
            return False
        
        self.ufid[root1] = root2
        
        return True

class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        
        connections.sort(key = lambda x : x[2])
        uf = UnionFind(N)
        cost = 0
        vertices = set()
        for fro, to, w in connections:
            vertices.add(fro)
            vertices.add(to)
            if uf.union(fro, to):
                cost += w
        # checking if all the vertices are accounted for
        if len(vertices) != N: 
            return -1
        conn = set()
       # making sure there is only one connected component
        for i in range(1, N):
            conn.add(uf.find(i))
        
        return cost if len(conn) == 1 else -1
        

1
Reply
Share
Report
sh0gg0th's avatar
Read More

Python code, using min heap instead of sorting (this will give us a better time complexity in cases where there are many duplicate connections with higher costs that we never end up using):

import heapq

class Solution:
    def minimumCost(self, N: int, connections: List[List[int]]) -> int:
        def find(i):
            if parent[i] != i: parent[i] = find(parent[i])
            return parent[i]
        
        parent, rank = list(range(N+1)), [0]*(N+1)
        connections = [[cost, u, v] for u, v, cost in connections]
        heapq.heapify(connections)
        res = cnt = 0
        
        while connections and cnt < N-1:
            cost, u, v = heapq.heappop(connections)
            u_par, v_par = find(u), find(v)
            if u_par != v_par:
                cnt += 1
                res += cost
                if rank[u_par] < rank[v_par]: parent[u_par] = v_par
                else:
                    parent[v_par] = u_par
                    if rank[u_par] == rank[v_par]: rank[u_par] += 1
        
        return res if cnt == N-1 else -1

0
Reply
Share
Report
lattices's avatar
Read More

The time complexity seems wrong. It should be O(MlogM + M) not O(M)

0
Reply
Share
Report
abdelrady0's avatar
Read More

kruskal algorithm is much easier

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.